The present invention relates generally to the data processing field, and more particularly, relates to a method and apparatus for scheduling data accesses for random access storage devices with a shortest access chain scheduling algorithm.
In random access storage devices, such as hard disk and CD-ROM drives, the data to be accessed next is chosen from a list of outstanding commands. The list of outstanding commands is referred to as a queue. The act of choosing the next command is known as scheduling. In general, the goal of the scheduling algorithm is to minimize the average access time for its commands. Many scheduling methods have been used including Shortest-Seek First (SSF), Shortest-Latency First (SLF), and Shortest-Access Time First (SATF). These algorithms share one thing in common, they only look at what the next command will be when choosing the best candidate. This is similar to a chess player only looking at the next move to make without considering his opponent""s next move. In the case of a chess player, only looking one move ahead results in poor play. In the case of scheduling commands, this results in poor performance.
A need exists for an improved scheduling algorithm for random access storage devices.
A principal object of the present invention is to provide a method and apparatus for scheduling commands for random access storage devices with a shortest access chain scheduling algorithm. Other important objects of the present invention are to provide such a method and apparatus for scheduling commands for random access storage devices with a shortest access chain scheduling algorithm substantially without negative effect; and that overcome many of the disadvantages of prior art arrangements.
In brief, a method and apparatus are provided for scheduling commands for random access storage devices with a shortest access chain scheduling algorithm. A plurality of possible chains for a queue of commands are processed. The plurality of possible chains are compared to identify one of the plurality of possible chains having a predetermined property. A first command of the identified one chain is selected as a next command to execute.
In accordance with features of the invention, the predetermined property includes, for example, a shortest access time or a lowest energy usage.